|
In recursive function theory, double recursion is an extension of primitive recursion which allows the definition of non-primitive recursive functions like the Ackermann function. Raphael M. Robinson called functions of two natural number variables ''G''(''n'', ''x'') double recursive with respect to ''given functions'', if * ''G''(0, ''x'') is a given function of ''x''. * ''G''(''n'' + 1, 0) is obtained by substitution from the function ''G''(''n'', ·) and given functions. * ''G''(''n'' + 1, ''x'' + 1) is obtained by substitution from ''G''(''n'' + 1, ''x''), the function ''G''(''n'', ·) and given functions. Robinson goes on to provide a specific double recursive function (originally defined by Rózsa Péter) * ''G''(0, ''x'') = ''x'' + 1 * ''G''(''n'' + 1, 0) = ''G''(''n'', 1) * ''G''(''n'' + 1, ''x'' + 1) = ''G''(''n'', ''G''(''n'' + 1, ''x'')) where the ''given functions'' are primitive recursive, but ''G'' is not primitive recursive. In fact, this is precisely the function now known as the Ackermann function. == See also == * Primitive recursion * Ackermann function 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Double recursion」の詳細全文を読む スポンサード リンク
|